#include <stdio.h>

int GetMidi(int* a,int left,int right)
{
    int midi=(left+right)/2;
    if(a[left]<a[midi])
    {
        if(a[midi]<a[right])
        return midi;
        else if(a[right]<a[left])
        return left;
        else
        return right;
    }
    else//(a[left]>a[midi])
    {
        if(a[right]>a[left])
        return left;
        else(a[right]<a[midi])
        return midi;
        else
        return right;
    }
}
void QuickSort(int *a,int left,int right)
{
    if(left>=right)
    return;
  if(right-left+1<10)
 {
    InsertSort(a,right-left+1);
 }    
  else
 {
    int midi=GetMidi(a,left,right);
    int begin = left;
    int end = right;
    int keyi = left;
    
    while(begin<end)
    {
        while(a[end]>=a[keyi]&&begin<end)
        {
            --end;
        }
        while(a[begin]<=a[keyi]&&begin<end)
        {
            --begin;
        }
        Swap(&a[begin],&a[end]);
    }
    Swap(&a[keyi],&a[begin]);
    keyi=begin;
    QuickSort(a,left,keyi-1);
    QuickSort(a,keyi+1,right);
    
 }
}